Current cross-certificates based Private Key Infrastructure (PKI) trust mechanisms, such as the Federal PKI Bridge, suffer from a scaling problem. Even given the topological simplification of the Federal Bridge Certificate Authority (CA), as trust bridges grow in size and complexity, the number of possible routes between a user and a relying party increase exponentially with each added CA, so that the time required for path discovery can increase beyond a tolerable delay for real-time operation. For example, up to 35 minutes for one Federal Bridge transaction has recently been reported. The standards that govern PKI, primarily X.509 and Request For Comments 3280 (RFC3280), envision a mechanism for a “relying party” in one PKI domain to accept credentials from a “user” in another domain. The relying party has one or more “trust anchors,” referred to as “certificate authorities” (CAs) that the relying party trusts completely. These CAs can create cross-certificates, which specify the other CAs that this CA trusts. This process of creating cross-certificates can be repeated multiple times, resulting in a chain of trust of bridges from the trust anchor to the user/sender's certificate. However, this chain of trust must be evaluated in real time, and entails finding all the possible chain(s) of certificates between the user/sender and the trust anchor(s). This would be challenging enough even if all the certificates in the world were immediately available to select from. Generally, the only inputs to the chain of trust builder are the end-points: the user's certificate, which is available because it is included, e.g., as part of the Secure Sockets Layer version 3 (SSLv3) connection protocol, and the trust-anchor(s)', which are part of the relying party's configuration.
Building a trust chain therefore involves an iterative process of sniffing out and recovering from the Internet each “next possible link” and building the chain one link at a time. This trust chain building requirement is true for any PKI-based protocol in which a PKI certificate is exchanged as part of building the trust chain.
The dilution of trust expands exponentially with the size of the trust bridge, similar to the time to validate a remote user's certificate. For example, what does it really mean to explicitly trust the entire Department of Defense (DoD) population? When trust is further bridged with the entire Federal government workforce, the problem becomes worse. When external sources, such as the NIH-EDUCAUSE Bridge, are included to bring in all the Educational Institutes into the extended trust bridge, what does “trust” mean? In this example, the time to evaluate a PKI certificate approaches the intolerable, and the useable trust approaches zero.
This trust dilution is best illustrated with a further example. A University located in Wyoming grants access to sensitive information to users holding DoD certificates. For the purposes of this example, a subset of the users abuse their trust, and publish sensitive information at various sites on the Internet. Through audit logs, the identities of the likely offenders are established. What is the University to do? It may complain to the DoD, but the complaint is unlikely to result in any action, since it is impossible to terminate the Common Access Card (CAC) Identity without removing the offenders from their services. The University's only choices are to establish manual overrides for these users, possibly on hundreds of servers at the University or to deny all access to the DoD. By trusting everyone, the University has lost control of its data, and cannot carry out its legal obligations to protect sensitive data.
Secure Sockets Layer version 2 (SSLv2), which provides an encrypted channel and server authentication, is the gold standard of low value e-commerce sites. However, when the stakes are high, SSLv3, with client authentication, is required to positively establish, without repudiation, the identity of the user. The Secure Sockets Layer (SSL) standard requires the server to present, in the protocol handshake, a list of the Trusted Authorities that the server will accept as sources of user certificates. The standard does not provide for bridging functionality, so that in the example of a University server providing strongly authenticated access to 3,000 other Universities, the server would have to send all 3,000 University CA certificates to the end user, effectively disabling access by massively overloading the user's computer and his network. Again, the standards imply a solution that does not scale. The current prior art for large trusted root stores is the Microsoft Trusted Root Authority store, which does not accept new roots because of this very problem.
Another current system for providing cross-certificates for an organization, such as a University, is to establish a private PKI. However, it is expensive and difficult to establish a high assurance PKI using tokens, which are required for high assurance. The DoD has spent $800M (as of early 2004), and has not yet completed a high assurance PKI for its 4 Million users. Using the University as an example, where labor is “free,” to establish a high assurance PKI, including the cost of tokens, Local Registration authorities, etc., the cost can easily exceed $200 per user for an initial setup. In this example, the University has to provide local registration authorities wherever its target population resides. The University must convince that target population to carry “yet another token.” The University has to deal with the issues of maintaining the token password space and discovering when the privileges need to be revoked. Establishing a private PKI is not a practical solution; otherwise, major e-Commerce vendors would have adopted this method.
The original X.509v1 standard imposes a single hierarchical root in order to avoid the prior art problems as noted above. This standard, however, proved intractable from a practical standpoint, such as “who is the sole root?” The resulting X.509v3 standard allows an unlimited number of trusted roots, but does not provide any answers to scalability of numbers or of trust. For example, a wedding party of 100 guests can be managed, but this current system does not work well with 10,000 guests because of linear scaling N. If all guests are required to shake hands with each other guest, the problem explodes exponentially, to N*(N−1)/2.
FIG. 1 is a prior art identity certification system. A user 102 connects with an external Registration Authority 106 that wishes to establish an identity certificate and a private key of the user 102. Through a connection 104, the user 102 passes the data required by the external Registration Authority 106. Being satisfied of the identity of user 102, the external Registration Authority 106 makes a connection 112 to a smart card 114 that is being bound to the user 102. Typically, a Personal Identification Number (PIN) is set by collaboration with the user 102, and a public-private key pair is generated on the smart card 114. The identity private key 116 is retained on the smart card 114, and the public key is returned through a connection 112. This public key is securely passed to an external CA 110 through a connection 108. The external CA 110 returns a signed identity certificate 118 over the connection 108 to the external Registration Authority 106, which uses the connection 112 to load the identity certificate 118 onto the smart card 114. In the prior art system, if the user 102 wants access to another organization, the user 102 must go through the same process again, i.e., being issued another smart card. This is costly and inefficient.